/**
 * Copyright (C) 2002 Michael Green <mtgreen@cs.ucsd.edu>
 * 
 * Copyright (C) 2002 Paul Kube <kube@cs.ucsd.edu>
 * 
 * Copyright (C) 2005 Owen Astrachan <ola@cs.duke.edu>
 * 
 * Copyright (C) 2011 Hoa Long Tam <hoalong.tam@berkeley.edu> and Armin Samii
 * <samii@berkeley.edu>
 * 
 * This file is part of CS Boggle.
 * 
 * CS Boggle is free software: you can redistribute it and/or modify it under
 * the terms of the GNU General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later
 * version.
 * 
 * CS Boggle is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
 * A PARTICULAR PURPOSE. See the GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along with
 * CS boggle. If not, see <http://www.gnu.org/licenses/>.
 */

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class LexiconHashTable implements LexiconInterface {
	
	private HashEntry[] hashItems;
	private LexiconHashTable prefixes;
	private int size = 10;
	private static final int[] PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
	private int load = 0;
	private int conflicts = 0;
	
	public LexiconHashTable(int hashMax){
		size = hashMax;
		hashItems = new HashEntry[size];
		prefixes = new LexiconHashTable(size, false);
	}

	public LexiconHashTable(){
		hashItems = new HashEntry[size];
		prefixes = new LexiconHashTable(size, false);
	}
	
	/**
	 * Private constructor used only for the prefix table.
	 * @param hashMax				Initial hash table size
	 * @param includePrefixTable	Should be false to avoid infinite loopage.
	 */
	private LexiconHashTable(int hashMax, boolean includePrefixTable){
		if(includePrefixTable){
			new LexiconHashTable();
		}else{
			hashItems = new HashEntry[size];
			prefixes = null;
		}
	}
	
	/**
	 * Used by the hash function. Converts each letter of the alphabet a seperate prime number.
	 * @param letter	Letter to convert
	 * @return			Corresponding prime number
	 * @throws IllegalArgumentException
	 */
	private static int letterToPrime(char letter) throws IllegalArgumentException{
		switch(letter){
			case 'a':
				return PRIMES[0];
			case 'b':
				return PRIMES[1];
			case 'c':
				return PRIMES[2];
			case 'd':
				return PRIMES[3];
			case 'e':
				return PRIMES[4];
			case 'f':
				return PRIMES[5];
			case 'g':
				return PRIMES[6];
			case 'h':
				return PRIMES[7];
			case 'i':
				return PRIMES[8];
			case 'j':
				return PRIMES[9];
			case 'k':
				return PRIMES[10];
			case 'l':
				return PRIMES[11];
			case 'm':
				return PRIMES[12];
			case 'n':
				return PRIMES[13];
			case 'o':
				return PRIMES[14];
			case 'p':
				return PRIMES[15];
			case 'q':
				return PRIMES[16];
			case 'r':
				return PRIMES[17];
			case 's':
				return PRIMES[18];
			case 't':
				return PRIMES[19];
			case 'u':
				return PRIMES[20];
			case 'v':
				return PRIMES[21];
			case 'w':
				return PRIMES[22];
			case 'x':
				return PRIMES[23];
			case 'y':
				return PRIMES[24];
			case 'z':
				return PRIMES[25];
		}
		throw new IllegalArgumentException();
	}
	
	/**
	 * Hash function. 
	 * @param newItem string to hash
	 * @return	compressed hash value that corresponds to newItem
	 */	
	private int hashItem(String newItem){
		int value = 0;
		for(int i=0;i<newItem.length();i++){
			value += newItem.charAt(i) * i;
		}
		int prime = PRIMES[value % PRIMES.length];
		return (value + prime) % size;
	}
	
	/**
	 * Tests that:
	 * 		* The hash function will consistently return the same hash for the same strings
	 * 		* The hash function will give unique values to all words (without compression)
	 * @return true if all tests pass
	 */
	private static boolean testHashItem(){
		LexiconHashTable test = new LexiconHashTable(100);
		int hash1 = test.hashItem("a");
		int hash2 = test.hashItem("aa");
		int hash3 = test.hashItem("abc");
		int hash4 = test.hashItem("abcabc");
		int hash5 = test.hashItem("abcdefghijklmnopqrstuvqxyz");
		
		int hash6 = test.hashItem("a");
		int hash7 = test.hashItem("aa");
		int hash8 = test.hashItem("abc");
		int hash9 = test.hashItem("abcabc");
		int hash10= test.hashItem("abcdefghijklmnopqrstuvqxyz");
		
		if(hash1 != hash6){
			return false;
		}
		if(hash2 != hash7){
			return false;
		}
		if(hash3 != hash8){
			return false;
		}
		if(hash4 != hash9){
			return false;
		}
		if(hash5 != hash10){
			return false;
		}
		if(hash1 == hash2){
			return false;
		}
		if(hash3 == hash4){
			return false;
		}
		return true;
	}

	/**
	 * Hashes and inserts a string into the hash table, and doubles the capacity when load exceeds 50%.
	 * Also handles conflicts by adding them to a bucket's chain.
	 * @param item	string to insert.
	 */
	private void insert(String item){
		if(load>size/2){
			doubleCapacity();
		}
		int key = hashItem(item);
		if(hashItems[key]!=null){
			hashItems[key].add(item);	
			conflicts++;
		}else{
			hashItems[key] = new HashEntry(item);
		}
		load++;		
	}

	
	/**
	 * Inserts every prefix of a word into seperate prefix hash table
	 * @param word	The word to extract and insert prefixes from
	 */
	private void insertPrefixes(String word){
		if(word.length()>0){
			prefixes.insert(word);
			insertPrefixes(word.substring(0,word.length()-1));
		}
	}
	
	/**
	 * Tests the insert and insertPrefixes methods
	 * @return true if all tests pass.
	 */
	private static boolean testInsertAndPrefixes(){
		LexiconHashTable test = new LexiconHashTable();
		test.insert("hey");
		test.insert("hello");
		test.insert("hi");
		test.insertPrefixes("hey");
		test.insertPrefixes("hello");
		test.insertPrefixes("hi");
		
		if(!test.contains("hey")){
			return false;
		}
		if(!test.contains("hello")){
			return false;
		}
		if(!test.contains("hi")){
			return false;
		}
		if(!test.containsPrefix("h")){
			return false;
		}
		if(!test.containsPrefix("he")){
			return false;
		}
		if(!test.containsPrefix("hel")){
			return false;
		}
		if(!test.containsPrefix("hell")){
			return false;
		}
		return true;
	}
	
	/**
	 * Rehashes and doubles the capacity of the Hash Table.
	 */
	private void doubleCapacity(){
		size*=2;
		load=0;
		conflicts=0;
		HashEntry[] temp = hashItems;
		hashItems = new HashEntry[size];
		for(int i=0;i<temp.length;i++){
			if(temp[i]!=null){
				insert(temp[i].myEntry);
				if(!temp[i].myOverflow.isEmpty()){
					for(int j=0;j<temp[i].myOverflow.size();j++){
						insert((String)temp[i].myOverflow.get(j));
					}
				}
			}
		}
	}
	
	/**
	 * Tests that the double capacity function doubles the capacity and does not alter the table's contents.
	 * @return true if all tests pass.
	 */
	private static boolean testDoubleCapacity(){
		LexiconHashTable test = new LexiconHashTable(10);
		
		if(test.size!=10){
			return false;
		}
		
		test.insert("dog");
		test.insert("cat");
		test.insert("monkey");
		test.insert("aardvark");
		test.doubleCapacity();
		
		if(test.size!=20){
			return false;
		}
		if(!test.contains("dog")){
			return false;	
		}
		if(!test.contains("cat")){
			return false;
		}
		if(!test.contains("monkey")){
			return false;
		}
		if(!test.contains("aardvark")){
			return false;
		}
		return true;
	}

	/**
	 * Load the words from an input source and store them in this lexicon.
	 * 
	 * @param input A scanner that will provide the entire dictionary.
	 */
    public void load(Scanner input) {		
        while (input.hasNext()) {
            String nextStr = input.next();

            insert(nextStr);
            if(prefixes!=null){
            	insertPrefixes(nextStr);
            }
        }
    }
    
    /**
     * If the prefix is in the lexicon, returns true.
     * 
     * @param s The word to search for.
     * @return True if the lexicon contains s.
     */
    public boolean containsPrefix(String s) {
		return prefixes.contains(s);
    }
    
    /**
     * Provides access to this hash table's array.
     * @param key	location to access in array.
     * @return 		hashItem's value at key, or null if key is invalid.
     */
    private HashEntry getValue(int key){
    	if(key<hashItems.length){
    		return hashItems[key];
    	}else{
    		return null;
    	}
    }
    
    /**
     * If the word is in the lexicon, returns true.
     * 
     * @param s The word to search for.
     * @return True if the lexicon contains s.
     */
    public boolean contains(String s){
		int key = hashItem(s);
		if(hashItems[key]!=null){
			return hashItems[key].look(s);
		}else{
			return false;
		}
    }
	
    /**
     * Inner bucket class. Implements chaining. 
     * @author Austen
     *
     */
	private static class HashEntry{
		private String myEntry;
		ArrayList<String> myOverflow;
		public HashEntry(String entry){
			myEntry = entry;
			myOverflow = new ArrayList<String>();
		}
		
		public HashEntry(){
			myEntry = new String();
			myOverflow = new ArrayList<String>();
		}
		
		/**
		 * Adds the given string to the bucket. If the bucket is already full, it adds it to the overflow chain instead
		 * @param newEntry	New string to add.
		 */
		public void add(String newEntry){
			if(myEntry!=null){
				myOverflow.add(newEntry);
			}else{
				myEntry = newEntry;
			}
		}
		
		/**
		 * Finds out if a given string is contained somehwere inside the bucket.
		 * If the chain is not empty, it checks there as well.
		 * @param s String to look for
		 * @return True if s is somewhere inside this bucket	
		 */
		public boolean look(String s){
			if(myOverflow.isEmpty()){
				return myEntry.equals(s);
			}else{
				return myEntry.equals(s) || myOverflow.indexOf(s)!=-1;
			}
		}
	}
	
	/**
	 * Tests the add and look methods of the HashEntry class
	 * @return true if all tests pass
	 */
	private static boolean testHashEntry(){
		HashEntry test = new HashEntry();
		if(test.look("word")){
			return false;
		}
		
		test.add("word");
		if(!test.look("word")){
			return false;
		}
		
		test.add("word2");	
		test.add("word3");
		if(!test.look("word")){
			return false;
		}
		if(!test.look("word2")){
			return false;
		}
		if(!test.look("word3")){
			return false;
		}
		return true;
	}

	@Override
	public Iterator<String> iterator() {
		return new HashIterator();
	}
	
	/**
	 * Hash class iterator. Returns strings, not buckets, in no particular order. 	 * 
	 * @author Austen
	 *
	 */
	private class HashIterator implements Iterator<String>{
		int nextValue;
		int visited = 0;
		int nextOverflow = 0;
		public HashIterator(){
			nextValue=0;
			restoreInvariant();
		}
		@Override
		public boolean hasNext() {
			return nextValue!=-1;
		}

		@Override	
		/**
		 * Returns the next available string in the hashItems array or the next availabe string in a bucket's chain.
		 */
		public String next() {
			HashEntry toReturn = hashItems[nextValue];
			visited++;
			if(toReturn.myOverflow.isEmpty() || nextOverflow >= toReturn.myOverflow.size()){
				nextOverflow = 0;
				nextValue++;
				restoreInvariant();	
				return toReturn.myEntry;			
			}else{
				int currOverflow = nextOverflow;
				nextOverflow++;
				return toReturn.myOverflow.get(currOverflow);
			}
		}
		
		/**
		 * Restores the invariant that nextValue is always the next bucket to search.
		 */
		private void restoreInvariant(){
			while(getValue(nextValue)==null){
				if(nextValue>=hashItems.length || visited > load){
					nextValue=-1;
					return;
				}else{
					nextValue++;
				}
			}
		}

		@Override
		public void remove() {
			// TODO Auto-generated method stub
			
		}
		
	}
	/**
	 * Tests private functions and returns and integer based on which one failed first.
	 * @return	0 if all tests passed, or a number depending on which test failed first.
	 */
	public static int testPrivateFunctions(){
		if(!LexiconHashTable.testHashItem()){
			return 1;
		}
		if(!LexiconHashTable.testInsertAndPrefixes()){
			return 2;
		}
		if(!LexiconHashTable.testDoubleCapacity()){
			return 3;
		}
		if(!LexiconHashTable.testHashEntry()){
			return 4;
		}
		return 0;
	}
}
